package offer;

/**
 * @author Jonny Long
 * @date 2021/3/22 19:06
 */
public class Solution416 {
    // dp[i][j]表示从数组的[0, i]这个子区间内挑选一些正整数
    // 每个数只能用一次，使得这些数的和恰好等于j。
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][sum / 2 + 1];
        /**
         * dp[..][0] = true 和 dp[0][..] = false
         * 背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。
         */
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum / 2; j++) {
                if (j < nums[i - 1] ) {
                    // 背包容量不足，不能装入第i个物品，取上个状态
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 装入或不装入背包
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
                System.out.printf("dp[%d][%d] = %b\n",i,j,dp[i][j]);
            }
            System.out.println("***********************");
        }
        return dp[n][sum / 2];
    }
}
